package search;

class Solution {
    public static int pivotIndex(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        if(nums.length == 0)
            return -1;
        int sumL = nums[i], sumR = nums[j];
        while(i != j){
            if(Math.abs(sumL) >= Math.abs(sumR)){
                j --;
                sumR += nums[j];
            }else if(Math.abs(sumL) < Math.abs(sumR)){
                i ++;
                sumL += nums[i];
            }
        }
        if(sumL == sumR)
            return i;
        return -1;
    }
    //worst case can be O(N^2)
    // can be optimize to use two way tranverse which implement the rule from both left end and right end

    public static void main(String[] args) {
        System.out.println(pivotIndex(new int[]{-1,-1,-1,0,1,1}));

    }
}